#include "headfiles.h"

using namespace std;
/*
string longestPalindrome(string s) {
    int size = s.length();
    int max_len = 0;
    int i, k, start;
    for (i = 0; i < size; i++) {
        // case 1
        for (k = 0; k < size; k++) {
            if (i - k < 0 || i + 1 + k >= size) {
                break;
            }
            if (s[i - k] == s[i + 1 + k]) {
                if (max_len < 2 + 2 * k) {
                    max_len = 2 + 2 * k;
                    start = i - k;
                }
            }
            else {
                break;
            }
        }
        
        // case 2
        for (k = 0; k < size; k++) {
            if (i - k < 0 || i + k >= size) {
                break;
            }
            
            if (s[i - k] == s[i + k]) {
                if (max_len < 1 + 2 * k) {
                    start = i - k;
                    max_len = 1 + 2 * k;
                }
            }
            else {
                break;
            }
        }
    }
    
    return s.substr(start, max_len);
}
*/

string longestPalindrome(string s) {
    string t;
    t.push_back('^');
    t.push_back('#');
    int i, size = s.length();
    for (i = 0; i < size; i++) {
        t.push_back(s[i]);
        t.push_back('#');
    }
    t.push_back('$');

    int r, c;
    int *p = new int[t.size() + 1];
    if (p == NULL) {
        cout << "Allocate buffer error!" << endl;
        return string("");
    }
    memset(p, 0, sizeof(int) * t.size());

    int t_size = t.size();
    r = c = 0; 
    for (i = 1; i < t_size; i++) {
        int i_mirror = 2 * c - i;
        if (r > i) {
            p[i] = min(r - i, p[i_mirror]);
        }
        else {
            p[i] = 0;
        }

        while (t[i - 1 - p[i]] == t[i + 1 + p[i]]) {
            p[i]++;
        }

        if (i + p[i] > r) {
            r = i + p[i];
            c = i;
        }
    }

    int max_len = 0;
    int center = 0;
    for (i = 1; i < t_size; i++) {
        if (max_len < p[i]) {
            max_len = p[i];
            center = i;
        }
    }

    return s.substr((center - 1 - max_len) / 2, max_len);
}

